|
The structured program theorem, also called Böhm-Jacopini theorem, is a result in programming language theory. It states that a class of control flow graphs (historically called charts in this context) can compute any computable function if it combines subprograms in only three specific ways (control structures). These are #Executing one subprogram, and then another subprogram (sequence) #Executing one of two subprograms according to the value of a boolean expression (selection) #Executing a subprogram until a boolean expression is true (iteration) The structured chart subject to these constraints may however use additional variables in the form of bits (stored in an extra integer variable in the original proof) in order to keep track of information that the original program represents by the program location. The construction was based on Böhm's programming language P′′. == Origin and variants == The theorem is typically credited〔 to a 1966 paper by Corrado Böhm and Giuseppe Jacopini. David Harel wrote in 1980 that the Böhm–Jacopini paper enjoyed "universal popularity",〔 particularly with proponents of structured programming. Harel also noted that "due to its rather technical style (1966 Böhm–Jacopini paper ) is apparently more often cited than read in detail"〔 and, after reviewing a large number of papers published up to 1980, Harel argued that the contents of the Böhm–Jacopini proof was usually misrepresented as a folk theorem that essentially contains a simpler result, a result which itself can be traced to the inception on modern computing theory in the papers of von Neumann and Kleene.〔 Harel also writes that the more generic name was proposed by H.D. Mills as "The Structure Theorem" in the early 1970s. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Structured program theorem」の詳細全文を読む スポンサード リンク
|